
"""
493. 翻转对
"""
from typing import List


class Solution:

    def __init__(self):
        self.tmp = []
        self.count = 0

    """
     * 方法2，利用归并排序
     * 思路：在归并排序的合并两个有序数组的位置中，在合并前统计左子树元素在右子树中满足nums[i] > 2 * nums[j]
     * 小问题：如何保证i < j的，因为在归并排序中，无论如何交换元素的位置，右子树的i永远小于左子树
    """
    def reversePairs(self, nums: List[int]) -> int:
        self.tmp = [nums[i] for i in range(len(nums))]
        self.gbSort(nums, 0, len(nums) - 1)
        return self.count

    """
     * 归并排序
     * 归并排序可以理解为二叉树，先将左子树排序，再将右子树排序，最后再将左右子树合并排序
     * 如何将数组分解为二叉树，以中心点为分割线，将数组分解为二叉树，叶子结点为数组元素
    """

    def gbSort(self, nums: List[int], low, high):
        if low == high:
            return

        # 中心点
        mid = low + int((high - low) / 2)

        # 排序左子树
        self.gbSort(nums, low, mid)
        # 排序右子树
        self.gbSort(nums, mid + 1, high)

        # 合并两个有序数组
        self.mergin_nums(nums, low, mid, high)

    def mergin_nums(self, nums: List[int], low, mid, high):
        i = low
        j = mid + 1
        for k in range(low, high + 1):
            self.tmp[k] = nums[k]

        # 统计“翻转对”
        end = mid + 1
        for m in range(low, mid + 1):
            while end <= high and nums[m] > 2 * nums[end]:
                end += 1
            self.count += end - (mid + 1)

        # 开始合并
        k = low
        while i <= mid or j <= high:
            if i > mid:
                nums[k] = self.tmp[j]
                j += 1
            elif j > high:
                nums[k] = self.tmp[i]
                i += 1
            elif self.tmp[i] < self.tmp[j]:
                nums[k] = self.tmp[i]
                i += 1
            else:
                nums[k] = self.tmp[j]
                j += 1
            k += 1